package com.theeviljames.countdown;

import java.util.Arrays;
import java.util.Random;
import java.util.Stack;
import java.util.Vector;

public class CountDown {

	private static final Random rand = new Random();
	private int POPSIZE;
	private int target;
	private GAStack[] pop;
	private int topscore;
	private Vector<Integer> numbers = new Stack<Integer>();;
	
	private int sumOfRanks;
	
	public CountDown(int popSize, int maxGenerations, int[] numbers, int target) {
		for(int i:numbers) this.numbers.add(i);
		GAStack best = null;
		POPSIZE = popSize;
		pop = new GAStack[POPSIZE];
		for(int i = 0; i < popSize; i++){
			GAStack ind = new GAStack();
			for(int z=0;z<numbers.length;z++) ind.add(numbers[z]);
			for(int z=0;z<4;z++) ind.add(Fitness.OPS[rand.nextInt(4)]);
			for(int z=0;z<100;z++){
				ind.mutateOps(1);
				ind.mutateMusicalChairs(1);
			}
			pop[i] = ind;	
		}
		this.target = target;
		Arrays.sort(pop);
		best = pop[0];
		sumOfRanks = (popSize*(popSize-1))/2;
		if((topscore = Fitness.score(pop[0],target))==0)  System.out.println("WOOOHOOOOO");
		GAStack[] children = new GAStack[POPSIZE];
		boolean solutionNotFound = true;
		int counter = 1;
		while(solutionNotFound&&counter<maxGenerations){
			for(int i=0;i<POPSIZE/2;i++){
				GAStack p1 = randomIndividual();
				GAStack p2 = randomIndividual();
				children[2*i] = p1.getChild2(p2);
				children[2*i+1] = p2.getChild2(p1);
			}
			pop = children;
			Arrays.sort(pop);
			if(Fitness.score(pop[0],target) < Fitness.score(best, target)) best = pop[0];
			if((topscore = Fitness.score(pop[0],target))==0) {
				System.out.println("Solution found!!!!");
				solutionNotFound = !solutionNotFound;
			}
			counter++;
			if(true){
				//for(GAStack g:pop)System.out.println(g);
				//System.out.println("Top");
				//System.out.println(pop[0]);
			}
		}
		System.out.println(topscore);
		System.out.println(pop[0]);
		System.out.println("Found in >" + counter + " generations");
		System.out.println(best);
		//	System.out.println(g);
		//}
	}


	public GAStack randomIndividual(){
		
		double pos = rand.nextDouble() * sumOfRanks;
		int n = (int) ((1+Math.sqrt(1+8*pos))/2);
		return pop[POPSIZE-1-n];
	}
	
	private GAStack randomGenome(){
		GAStack result = new GAStack();
		Stack<Integer> big = new Stack<Integer>();
		for(int i = 0; i < 4; i++)big.push((i+1)*25);
		Stack<Integer> small= new Stack<Integer>();
		for(int i = 1; i <= 20; i++)small.push((i+1)/2);
		int noOfBig = rand.nextInt(5);
		int noOfSmall= 6-noOfBig;
		for(int i = 0; i < noOfBig; i++){
			result.add(rand.nextInt(result.size()+1),big.remove(rand.nextInt(big.size())));
		}
		for(int i = 0; i < noOfSmall; i++){
			result.add(rand.nextInt(result.size()+1),small.remove(rand.nextInt(small.size())));
		}
		for(int i = 0; i < 5; i++){
			result.add(rand.nextInt(result.size()+1), Fitness.OPS[rand.nextInt(Fitness.OPS.length)]);
		}
		return result;
	}
	
	public class GAStack extends Stack<Integer> implements Comparable<Stack>{
		public GAStack() {
			// TODO Auto-generated constructor stub
		}
		public GAStack(int size) {
			super.setSize(size);
		}
		public int compareTo(Stack arg0) {
			int a = Fitness.score(this,target);
			int b = Fitness.score(arg0,target);
			return a-b;
		}
		public GAStack getChild(GAStack other){
			int cutoff = CountDown.rand.nextInt(size());
			GAStack child = new GAStack();
			for(int i = 0; i < cutoff; i++)child.add(i, this.get(i));
			for(int i = cutoff; i < size(); i++)child.add(i, other.get(i));
			child.mutateOps(0.5);
			child.mutateMusicalChairs(0.5);
			return child;
		}
		public GAStack getChild2(GAStack other){
			GAStack child = new GAStack(size());
			Vector<Integer> nums = (Vector<Integer>)numbers.clone();
			GAStack me,her;
			if(rand.nextDouble()<0.5)	{me = this;her = other;}
			else 						{me = other;her = this;}
			for(int i = 0; i < size(); i++){
				int p1 = me.get(i);
				if(p1>Integer.MAX_VALUE-4)
					child.set(i, p1);
				else{
					if(!nums.contains(p1)){
						if(!nums.contains(other.get(i))){
							child.set(i, nums.remove(rand.nextInt(nums.size())));
						} else {
							child.set(i, other.get(i));
							nums.remove(nums.indexOf(other.get(i)));
						}
					} else {
						child.set(i, p1);
						nums.remove(nums.indexOf(p1));
					}
				}
				
			}
			child.mutateOps(0.3);
			child.mutateMusicalChairs(0.3);
			return child;
		}
		
		public void mutateOps(double prob){
			for(int i=0;i<size();i++){
				if(get(i) > Integer.MAX_VALUE-4){
					if(rand.nextDouble()<= prob) set(i,Fitness.OPS[rand.nextInt(4)]);
				}
			}
		}
		public void mutateMusicalChairs(double prob){
			for(int i=0;i<size();i++){
				if(rand.nextDouble()<= prob){
					int out = remove(rand.nextInt(size()));
					int inPos = rand.nextInt(size());
					add(inPos,out);
				}
			}
		}
		@Override
		public synchronized String toString() {
			return toExpression((GAStack)this.clone())+" "+Fitness.score(this, target);
		}
		private final String toExpression(GAStack stack){
			int elem = stack.pop();
			String result = "";
			switch(elem){
				case Fitness.PLUS: 
					result += "(";
					result += toExpression(stack);
					result += "+";
					result += toExpression(stack);
					result += ")";
					break;
				case Fitness.MINUS:
					result += "(";
					result += toExpression(stack);
					result += "-";
					result += toExpression(stack);
					result += ")";
					break;
				case Fitness.MULT: 
					result += "(";
					result += toExpression(stack);
					result += "*";
					result += toExpression(stack);
					result += ")";
					break;
				case Fitness.DIV:
					result += "(";
					result += toExpression(stack);
					result += "/";
					result += toExpression(stack);
					result += ")";
					break;
				default:
					result += elem;
					break;
				
			}
			return result;
		}	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Au	to-generated method stub
		CountDown cd = new CountDown(1000, 10000,new int[]{2,25,9,8,3,7},547);
	}

}
